package com.learn.tree;

public class MaxTreeDistance {
    public static class Node {
        private Node left;
        private Node right;
        private int value;

        public Node(int value) {
            this.value = value;
        }
    }

    public static class Info {
        private int maxDistance;
        private int height;

        public Info(int height, int maxDistance) {
            this.height = height;
            this.maxDistance = maxDistance;
        }
    }

    public int getMaxDistance(Node head) {
        return process(head).maxDistance;
    }

    public Info process(Node node) {
        if (node == null) {
            return new Info(0, 0);
        }

        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);
        int length = Math.max(leftInfo.height, rightInfo.height) + 1;

        int maxDistance = Math.max(Math.max(leftInfo.maxDistance, rightInfo.maxDistance), leftInfo.height + 1 + rightInfo.height);
        return new Info(length, maxDistance);

    }

}
